package com.zs.letcode.binary_search;

/**
 * 寻找比目标字母大的最小字母
 * 给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母target，请你寻找在这一有序列表里比目标字母大的最小字母。
 * <p>
 * 在比较时，字母是依序循环出现的。举个例子：
 * <p>
 * 如果目标字母 target = 'z' 并且字符列表为letters = ['a', 'b']，则答案返回'a'
 * <p>
 * <p>
 * 示例：
 * <p>
 * 输入:
 * letters = ["c", "f", "j"]
 * target = "a"
 * 输出: "c"
 * <p>
 * 输入:
 * letters = ["c", "f", "j"]
 * target = "c"
 * 输出: "f"
 * <p>
 * 输入:
 * letters = ["c", "f", "j"]
 * target = "d"
 * 输出: "f"
 * <p>
 * 输入:
 * letters = ["c", "f", "j"]
 * target = "g"
 * 输出: "j"
 * <p>
 * 输入:
 * letters = ["c", "f", "j"]
 * target = "j"
 * 输出: "c"
 * <p>
 * 输入:
 * letters = ["c", "f", "j"]
 * target = "k"
 * 输出: "c"
 * <p>
 * <p>
 * 提示：
 * <p>
 * letters长度范围在[2, 10000]区间内。
 * letters 仅由小写字母组成，最少包含两个不同的字母。
 * 目标字母target 是一个小写字母。
 * 相关标签
 * 数组
 * 二分查找
 * <p>
 * Python3
 * <p>
 * <p>
 * <p>
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/binary-search/xeiuui/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/7/31 09:57
 */
public class Chapter13 {
    public static void main(String[] args) {

    }

    private static class Solution {
        /**
         * 方法一：记录存在的字母
         *
         * @param letters
         * @param target
         * @return
         */
        public char nextGreatestLetter(char[] letters, char target) {
            boolean[] seen = new boolean[26];
            for (char c : letters) {
                seen[c - 'a'] = true;
            }
            while (true) {
                target++;
                if (target > 'z') target = 'a';
                if (seen[target - 'a']) return target;
            }
        }

        /**
         * 方法二：线性扫描
         */
        public char nextGreatestLetter1(char[] letters, char target) {
            for (char c : letters) {
                if (c > target) return c;
            }
            return letters[0];
        }

        /**
         * 方法三：二分查找
         */
        public char nextGreatestLetter2(char[] letters, char target) {
            int lo = 0, hi = letters.length;
            while (lo < hi) {
                int mid = (lo + hi) / 2;
                if (letters[mid] <= target) lo = mid + 1;
                else hi = mid;
            }
            return letters[lo % letters.length];
        }
    }
}
